//KV模型的AVLTree
#pragma once
#include <utility>
#include <cassert>
#include <iostream>
using namespace std;
template <class K,class V>
struct AVLTreeNode
{
public:
  AVLTreeNode(const pair<K,V>& kv)
  :_left(nullptr)
  ,_right(nullptr)
  ,_parent(nullptr)
  ,_kv(kv)
  ,_bf(0)
  {}
  AVLTreeNode<K,V>* _left;
  AVLTreeNode<K,V>* _right;
  AVLTreeNode<K,V>* _parent;

  pair<K,V> _kv;

  int _bf;//平衡因子balance factor

};

template<class K,class V>
class AVLTree 
{
  typedef AVLTreeNode<K,V> Node;
public:
  bool insert(const pair<K,V>& kv)
  {
    if(_root==nullptr)
    {
      _root=new Node(kv);
      return true;
    }
    Node* parent=nullptr;
    Node* cur=_root;
    while(cur)
    {
      if(kv.first<cur->_kv.first)
      {
        parent=cur;
        cur=cur->_left;
      }
      else if(kv.first>cur->_kv.first)
      {
        parent=cur;
        cur=cur->_right;
      }
      else 
      {
        //kv.first==cur->_kv.first,说明已经存在，不需要插入
        return false;
      }
    }
    //cur==nullptr,可以开始插入了
    cur=new Node(kv);
    if(kv.first<parent->_kv.first)
    {
      parent->_left=cur;
    }
    else 
    {
      parent->_right=cur;
    }

    cur->_parent=parent;

    //插入工作完成，但是新插入的节点会影响所有祖先节点的平衡因子，需要对应处理
    //1.向上逐步更新平衡因子
    //更新前，祖先节点的平衡因子有3种情况
    //(1).bf=0 (2).bf=1 (3). bf=-1
    //如何更新:插入在右边，则parentRightTree高度必然+1，即bf++，反之插入在左边则bf--
    //是否需要继续向上更新呢?如果parent->bf变为了0，则说明parentTree高度不变，此时无需向上更新
    //如果p->bf==-1或bf==1,则pTree高度增加了，还需要向上更新，判断和之前一致
    //如果p->bf==-2或bf==2,则pTree高度增加了，且此时已经不平衡了，需要先对pTree这棵树进行旋转处理，再判断是否更新平衡因子
    //循环向上更新，直到parent==nullptr更新完毕
    while(parent)
    {
      if(parent->_left==cur)
      {
        parent->_bf--;
      }
      else 
      {
        parent->_bf++;
      }

      if(parent->_bf==0)
      {
        break;
      }
      else if(parent->_bf==-1 || parent->_bf==1)
      {
        cur=parent;
        parent=parent->_parent;
      }
      else if(parent->_bf==2||parent->_bf==-2)
      {
        //相关处理
        if(parent->_bf==2 && cur->_bf==1)
        {
          //此时单纯的右边高，进行左单旋
          RotateL(parent);
        }
        else if(parent->_bf==-2&&cur->_bf==-1)
        {
          //此时单纯的左边高，进行右单旋
          RotateR(parent);
        }
        else if(parent->_bf==2&&cur->_bf==-1)
        {
          //此时右子树的左树变高导致右边高
          RotateRL(parent);
          //更新完毕
        }
        else if(parent->_bf==-2&&cur->_bf==1) 
        {
          RotateLR(parent);
        }
        else 
        {
          assert(false);
        }

        break;
      }
      else
      {
        //代码有问题
        assert(false);
      }
    }

    return true;
    
    
  }
  
  void InOrder()
  {
    _InOrder(_root);
    cout<<endl;
  }

  //验证AVL树:1.实现求高度的函数 2.判断此树是否是AVL树(高度计算平衡因子)以及左右子树是否是AVL树，递归判断
  int Highet()
  {
    return _Highet(_root);
  }

  bool IfAVLTree()
  {
    return _IfAVLTree(_root);
  }

private:
  void RotateL(Node* parent)
  {
    Node* subR=parent->_right;
    Node* subRL=subR->_left;

    Node* ppNode=parent->_parent;
    //subRL可能是空
    parent->_right=subRL;
    if(subRL)
      subRL->_parent=parent; 

    subR->_left=parent;
    parent->_parent=subR;

    //subR和原父亲节点的链接
    if(_root==parent)
    {
      _root=subR;
      _root->_parent=nullptr;
    }
    else 
    {
      if(ppNode->_left==parent)
      {
        ppNode->_left=subR;
      }
      else 
      {
        ppNode->_right=subR;
      }
      subR->_parent=ppNode;
    }

    //链接完毕，更正平衡因子
    subR->_bf=parent->_bf=0;
  }

  void RotateR(Node* parent)
  {
    Node* subL=parent->_left;
    Node* subLR=subL->_right;
    Node* ppNode=parent->_parent;

    parent->_left=subLR;
    if(subLR)
      subLR->_parent=parent;

    subL->_right=parent;
    parent->_parent=subL;

    if(_root==parent)
    {
      _root=subL;
      _root->_parent=nullptr;
    }
    else 
    {
      if(ppNode->_left==parent)
      {
        ppNode->_left=subL;
      }
      else 
      {
        ppNode->_right=subL;
      }
      subL->_parent=ppNode;
    }

    //平衡因子更新
    subL->_bf=parent->_bf=0;
  }

  void RotateRL(Node* parent)
  {
    Node* subR=parent->_right;
    Node* subRL=subR->_left;
    int bf=subRL->_bf;

    RotateR(subR);
    RotateL(parent);

    //更新平衡因子
    if(bf==0)
    {
      parent->_bf=subR->_bf=subRL->_bf=0;
    }
    else if(bf==-1)
    {
      parent->_bf=subRL->_bf=0;
      subR->_bf=1;
    }
    else if(bf==1)
    {
      parent->_bf=-1;
      subR->_bf=subRL->_bf=0;
    }
    else
    {
      assert(false);
    }
  }

  void RotateLR(Node* parent)
  {
    Node* subL=parent->_left;
    Node* subLR=subL->_right;
    int bf=subLR->_bf;

    RotateL(subL);
    RotateR(parent);
    //更新平衡因子
    parent->_bf=subL->_bf=subLR->_bf=0;
    if(bf==0)
    {
      //
    }
    else if(bf==-1)
    {
      parent->_bf=1;
    }
    else if(bf==1)
    {
      subL->_bf=-1;
    }
    else 
    {
      assert(false);
    }
  }

  void _InOrder(Node* root)
  {
    if(root==nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout<<root->_kv.first<<" ";
    _InOrder(root->_right);
  }

  int _Highet(Node* root)
  {
    if(root==nullptr)
    {
      return 0;
    }
    int lHighet=_Highet(root->_left);
    int rHighet=_Highet(root->_right);
    return 1+(lHighet>rHighet?lHighet:rHighet);
  }

  bool _IfAVLTree(Node* root)
  {
    if(root==nullptr)
      return true;

    int bf=_Highet(root->_right)-_Highet(root->_left);
    if(bf!=root->_bf)
    {
      cout<<"bf error1"<<endl;
      return false;
    }
    else if(bf>=2&& bf<=-2)
    {
      cout<<"bf error2"<<endl;
      return false;
    }
    else 
      return _IfAVLTree(root->_left) && _IfAVLTree(root->_right);
  }

  Node* _root=nullptr;
};
